package com.leetcode.程序员面试金典.medium;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2021-04-12 12:44
 */
public class 面试题_17_14_最小K个数 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] arr = {1,3,5,7,2,4,6,8};
    int k = 4;
    int[] smallestK = solution.smallestK(arr, k);
    System.out.println(Arrays.toString(smallestK));
  }

  static
  class Solution {
    public int[] smallestK(int[] arr, int k) {
      if (arr == null || arr.length == 0 || k <= 0) {
        return new int[0];
      }
      if (arr.length <= k) {
        return arr;
      }
      int[] bigTopHeap = Arrays.copyOf(arr, k);
      initBigTopHeap(bigTopHeap);
      for (int i = k; i < arr.length; ++i) {
        if (arr[i] < bigTopHeap[0]) {
          bigTopHeap[0] = arr[i];
          adjustBigTopHeap(0, bigTopHeap);
        }
      }
      return bigTopHeap;
    }

    private void initBigTopHeap(int[] bigTopHeap) {
      int lastIndex = (bigTopHeap.length - 2) / 2;
      for (int i = lastIndex; i >= 0; --i) {
        adjustBigTopHeap(i, bigTopHeap);
      }
    }

    private void adjustBigTopHeap(int index, int[] bigTopHeap) {
      while (index < bigTopHeap.length) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int maxValue = bigTopHeap[index];
        int maxValueIndex = index;
        if (left < bigTopHeap.length && bigTopHeap[left] > maxValue) {
          maxValue = bigTopHeap[left];
          maxValueIndex = left;
        }
        if (right < bigTopHeap.length && bigTopHeap[right] > maxValue) {
          maxValue = bigTopHeap[left];
          maxValueIndex = right;
        }
        if (maxValueIndex == index) {
          break;
        }
        swap(index, maxValueIndex, bigTopHeap);
        index = maxValueIndex;
      }
    }

    private void swap(int i, int j, int[] arr) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
  }

}
